#ifndef __BWLIB_DATA_STRUCT_UNION_FIND_SET_H__
#define __BWLIB_DATA_STRUCT_UNION_FIND_SET_H__
#include "../config.h"
#include "../utility/nullptr.h"
#include <cstring>
#include <stdexcept>

namespace bwlib
{
	class union_find_set
	{
	public:
		typedef std::size_t size_type;

		explicit union_find_set(size_type count)
		{
			__size = count;
			__father = new int[count + 1];
			__block_size = new int[count + 1];
			clear();
		}
		union_find_set(const union_find_set& other)
		{
			__size = other.__size;
			__father = new int[__size];
			__block_size = new int[__size];
			std::memcpy(__father,
				other.__father,
				__size * sizeof(int));
			std::memcpy(__block_size,
				other.__block_size,
				__size * sizeof(int));
		}
		const union_find_set& operator = (const union_find_set& other)
		{
			__clear_mem();
			__size = other.__size;
			__father = new int[__size];
			__block_size = new int[__size];
			std::memcpy(__father,
				other.__father,
				__size * sizeof(int));
			std::memcpy(__block_size,
				other.__block_size,
				__size * sizeof(int));
			return *this;
		}
		~union_find_set()
		{
			if(__father) delete[] __father;
			if(__block_size) delete[] __block_size;
		}

#ifdef __BWLIB_CXX11
		union_find_set(union_find_set&& other) __BWLIB_NOEXCEPT
		{
			__size = other.__size;
			other.__size = 0;
			__father = other.__father;
			other.__father = nullptr;
			__block_size = other.__block_size;
			other.__block_size = nullptr;
		}
		const union_find_set& operator = (union_find_set&& other)
		{
			__clear_mem();
			__size = other.__size;
			other.__size = 0;
			__father = other.__father;
			other.__father = nullptr;
			__block_size = other.__block_size;
			other.__block_size = nullptr;
			return *this;
		}
#endif
	public:
		/* @brief: （重新）初始化并查集
		   @complexity: O(n) */
		void clear()
		{
			__check();
			for(int i = 1; i <= size(); ++i)
			{
				__father[i] = i;
				__block_size[i] = 1;
			}
		}
		/* @brief: 获取并查集大小（元素个数）
		   @complexity: O(1) */
		size_type size() const __BWLIB_NOEXCEPT
		{
			return __size;
		}
		/* @brief: 拓展并查集元素个数
		   @complexity: O(size) */
		void inflate(size_type size)
		{
			if(size < this->size())
				throw std::runtime_error("bad union-find set size");
			bool clean = !__father && !__block_size;
			if(!clean) __check();
			int* temp_father = new int[size + 1];
			int* temp_block_size = new int[size + 1];
			if(!clean)
			{
				std::memcpy(temp_father, __father,
					sizeof(int) * this->size());
				std::memcpy(temp_block_size, __block_size,
					sizeof(int) * this->size());
				__clear_mem();
			}
			__father = temp_father;
			__block_size = temp_block_size;
		}
		/* @brief: 交换两个并查集
		   @complexity: O(1) */
		void swap(union_find_set& other)
		{
			__clear_mem();
			__size = other.__size;
			other.__size = 0;
			__father = other.__father;
			other.__father = nullptr;
			__block_size = other.__block_size;
			other.__block_size = nullptr;
		}
	public:
		/* @brief: 查找指定元素所属的集合
		   @complexity: O(alpha) */
		int operator [](int elem)
		{
			return find(elem);
		}
		/* @brief: 查找指定元素所属的集合
		   @complexity: O(alpha) */
		int find(int elem)
		{
			__check();
#ifdef __BWLIB_SAFER_CHECK
			if(elem <= 0 || elem > size())
				throw std::runtime_error("bad union-find set elem");
#endif
			return __find(elem);
		}
		/* @brief: 获得指定元素所属集合的大小
		   @complexity: O(alpha) */
		int get_block_size(int elem)
		{
			return __block_size[find(elem)];
		}
		/* @brief: 获得指定元素所属集合的大小
		   @complexity: O(alpha) */
		bool union_elem(int u, int v)
		{
			u = find(u);
			v = find(v);
			if(u == v) return false;
			__father[u] = v;
			__block_size[v] += __block_size[v];
			return true;
		}
	private:
		int* __father;
		int* __block_size;
		size_type __size;

		void __check()
		{
#ifdef __BWLIB_SAFER_CHECK
			if(!__father || !__block_size)
				throw std::runtime_error("uninitialied union-find set");
#endif
		}

		void __clear_mem()
		{
			if(__father) 
			{
				delete[] __father;
				__father = nullptr;
			}

			if(__block_size)
			{
				delete[] __block_size;
				__block_size = nullptr;
			}
		}

		int __find(int elem) __BWLIB_NOEXCEPT
		{
			if(__father[elem] == elem)
				return elem;
			return __father[elem] = __find(__father[elem]);
		}
	};

	inline void swap(union_find_set& a, union_find_set& b)
	{
		a.swap(b);
	}
}

#endif
